
interface IHeap {
    /**
     * 堆的大小
     */
    heapSize: number;
    /**
     * 存放的数据
     */
    readonly data: number[];
    /**
     * 构造堆.
     */
    readonly MakeHeap?: () => void;
    /**
     * 返回最大元素
     */
    readonly Maximum?: () => number;
    /**
     * 返回最小元素
     */
    readonly Minimum?: () => number;
    /**
     * 抽取最大元素,置于末尾.
     */
    readonly ExtractMax?: () => number;
    /**
     * 抽取最小元素,置于末尾.
     */
    readonly ExtractMin?: () => number;
    /**
     * 将index处的元素值提升到key.
     * @param index 目标元素的索引
     * @param key 新的元素值
     */
    readonly IncreaseKey?: (index: number, key: number) => void;
    /**
     * 将index处的元素值降低到key.
     * @param index 目标元素的索引
     * @param key 新的元素值
     */
    readonly DecreaseKey?: (index: number, key: number) => void;
    /**
     * 维护最大堆的性质.
     * @param index 目标子树的根节点的索引
     */
    readonly MaxHeapify?: (index: number) => void;
    /**
     * 维护最小堆的性质.
     * @param index 目标子树的根节点的索引
     */
    readonly MinHeapify?: (index: number) => void;
}
/**
 * 最大堆
 */
export class MaxHeap implements IHeap {
    /**
     * 构造函数,构造一个最大堆.
     * 用于排序.
     * @param data 一个number类型的Array.  
     */
    constructor(...data: number[]) {
        this.data = data;
        this.heapSize = data.length;
        this.MakeHeap();
    }
    /**
     * 堆的大小
     */
    heapSize: number;
    /**
     * 存放的数据
     */
    readonly data: number[];
    /**
     * 构造堆.
     */
    MakeHeap () {
        for (let index = Math.floor(this.heapSize / 2); index >= 0; index--) {
            this.MaxHeapify(index);
        }
    }

    /**
     * 抽取最大元素,置于末尾.
     */
    ExtractMax (): number {
        if (this.heapSize < 1) {
            throw "HeapUnderFlow";
        }
        let max = this.data[0];
        this.data[0] = this.data[this.data.length - 1];
        this.heapSize--;
        this.MaxHeapify(0);
        return max;
    }
    /**
     * 返回最大元素
     */
    Maximum (): number {
        return this.data[0];
    }
    /**
     * 将index处的元素值提升到key.
     * @param index 目标元素的索引
     * @param key 新的元素值
     */
    IncreaseKey (index: number, key: number): void {
        if (this.data[index] > key) {
            throw "NewKeySmallThanOld";
        }
        this.data[index] = key;
        while (index > 0 && this.data[Parent(index)] < this.data[index]) {
            [this.data[index], this.data[Parent(index)]] = [this.data[Parent(index)], this.data[index]];
            index = Parent(index);
        }
    }
    /**
     * 排序这个堆,返回排序后的数组.
     * 
     * 注:Release v0.1.2 中已修改为Copy后排序
     */
    HeapSort (): number[] {
        var copy: MaxHeap = new MaxHeap(...this.data.slice());
        for (let i = copy.data.length - 1; i > 0; i--) {
            [copy.data[0], copy.data[i]] = [copy.data[i], copy.data[0]];
            copy.heapSize--;
            copy.MaxHeapify(0);
            // console.log(`${this},i=${i}`); //Test Work
        }
        return (copy.data);
    }
    /**
     * 维护最大堆的性质.
     * @param index 目标子树的根节点的索引
     */
    MaxHeapify (index: number) {
        let l = Left(index);
        let r = Right(index);
        let largest: number;
        if (l < this.heapSize && this.data[l] >= this.data[index]) {
            largest = l;
        }
        else {
            largest = index;
        }
        if (r < this.heapSize && this.data[r] >= this.data[largest]) {
            largest = r;
        }
        if (largest !== index) {
            [this.data[largest], this.data[index]] = [this.data[index], this.data[largest]]
            this.MaxHeapify(largest);
        }
    }
}
/**
 * 最小堆
 */
export class MinHeap implements IHeap {
    /**
     * 构造函数,构造一个最小堆.
     * 用于排序.
     * @param data 一个number类型的Array.  
     */
    constructor(...data: number[]) {
        this.data = data;
        this.heapSize = data.length;
        this.MakeHeap();
    }
    /**
     * 堆的大小
     */
    heapSize: number;
    /**
     * 存放的数据
     */
    readonly data: number[];
    /**
     * 构造堆.
     */
    MakeHeap () {
        for (let index = Math.floor(this.heapSize / 2); index >= 0; index--) {
            this.MinHeapify(index);
        }
    }

    /**
     * 抽取最小元素,置于末尾.
     */
    ExtractMin (): number {
        if (this.heapSize < 1) {
            throw "HeapUnderFlow";
        }
        let max = this.data[0];
        this.data[0] = this.data[this.data.length - 1];
        this.heapSize--;
        this.MinHeapify(0);
        return max;
    }
    /**
     * 返回最小元素
     */
    Minimum (): number {
        return this.data[0];
    }
    /**
     * 将index处的元素值降低到key.
     * @param index 目标元素的索引
     * @param key 新的元素值
     */
    DecreaseKey (index: number, key: number): void {
        if (this.data[index] > key) {
            throw "NewKeySmallThanOld";
        }
        this.data[index] = key;
        while (index > 0 && this.data[Parent(index)] < this.data[index]) {
            [this.data[index], this.data[Parent(index)]] = [this.data[Parent(index)], this.data[index]];
            index = Parent(index);
        }
    }
    /**
     * 排序这个堆,返回排序后的数组.
     * 
     * 注:Release v0.1.2 中已修改为Copy后排序
     */
    HeapSort (): number[] {
        var copy: MinHeap = new MinHeap(...this.data.slice());
        for (let i = copy.data.length - 1; i > 0; i--) {
            [copy.data[0], copy.data[i]] = [copy.data[i], copy.data[0]];
            copy.heapSize--;
            copy.MinHeapify(0);
            // console.log(`${this},i=${i}`); //Test Work
        }
        return (copy.data);
    }
    /**
     * 维护最小堆的性质.
     * @param index 目标子树的根节点的索引
     */
    MinHeapify (index: number) {
        let l = Left(index);
        let r = Right(index);
        let minimal: number;
        if (l < this.heapSize && this.data[l] <= this.data[index]) {
            minimal = l;
        }
        else {
            minimal = index;
        }
        if (r < this.heapSize && this.data[r] <= this.data[minimal]) {
            minimal = r;
        }
        if (minimal !== index) {
            [this.data[minimal], this.data[index]] = [this.data[index], this.data[minimal]]
            this.MinHeapify(minimal);
        }
    }
}
/**
 * 返回节点的左子节点.
 * @param index 目标节点的索引
 */
function Left (index: number): number {
    return (index + 1) * 2 - 1;
}
/**
 * 返回节点的右子节点.
 * @param index 目标节点的索引
 */
function Right (index: number): number {
    return (index + 1) * 2;
}
/**
 * 返回节点的父节点.
 * @param index 目标节点的索引
 */
function Parent (index: number): number {
    return Math.floor((index + 1) / 2);
}